package com.leetcode.No0032;

import org.junit.Test;

import java.util.HashMap;

/**
 * @program: leetcode
 * @description: 最长有效括号 最简单直接的原始方法
 * @author: wangzhihua
 * @date: 2021-06-27
 */
public class Solution01 {
	@Test
	public void test01() {
//		System.out.println(longestValidParentheses("()()()"));
		System.out.println(longestValidParentheses("(()()(())(("));
	}

	public int longestValidParentheses(String s) {
		int len = s.length();
		char[] brackets = s.toCharArray();
		boolean[] isUsed = new boolean[len];

		// range 和 i 的for语句配合，意思是 i 和 i+range 这两个字符是否能配成一对
		for (int range = 1; range <= len; range += 2) {
			for (int i = 0; i + range < len; ) {
				if (isUsed[i] || isUsed[i + range] || brackets[i] != '(' || brackets[i + range] != ')') {
					++i;
					continue;
				}
				int j = locatingUnusedSubscripts(i + 1, i + range - 1, isUsed);
				if (j == i + range) {
					isUsed[i] = true;
					isUsed[j] = true;
					i = j + 1;
				} else {
					i = j;
				}
			}
		}

		int ans = 0;
		int tmpAns = 0;
		for (int i = 0; i < len; ++i) {
			if (isUsed[i]) {
				++tmpAns;
				ans = Math.max(ans, tmpAns);
			} else {
				tmpAns = 0;
			}
		}

		return ans;
	}

	// 遍历范围[start, end]，返回值表示没有成对的第一个字符的下标
	private int locatingUnusedSubscripts(int start, int end, boolean[] isUsed) {
		int index = start;
		while (index <= end) {
			if (!isUsed[index]) {
				break;
			}
			++index;
		}
		return index;
	}

}
